# -*- coding: utf-8 -*-

"""剑指 Offer II 085. 生成匹配的括号
正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

提示：
1 <= n <= 8"""

class Solution:
    """排列组合，选取有效组合，用回溯+递归；
    剪枝：
    用正负来表示当前组合状态，状态不能小于0；当状态大于0，前后括号皆可取；当状态等于0，只能取前括号
    用字典 {'(': 3, ')': 3} 来表示还可以取的原料池
        优化成 {1: 3, -1: 3}，表示如果取'('，状态可+1， 反之亦然"""
    def generateParenthesis(self, n: int):
        answer, pool, state, ref = [], {1: n, -1: n}, 0, {1:'(', -1: ')'}
        def fork(pool, state, group):
            if not pool:
                answer.append(group)
                return
            
            if state > 0:
                for p in pool.keys():
                    pool_new = pool.copy()
                    state_new = state+p
                    group_new = group + ref[p]
                    if pool_new[p] > 1:
                        pool_new[p] -= 1
                    else:
                        del pool_new[p]
                    fork(pool_new, state_new, group_new)
            else:
                if 1 in pool.keys():
                    pool_new = pool.copy()
                    state_new = state+1
                    group_new = group + '('
                    if pool_new[1] > 1:
                        pool_new[1] -= 1
                    else:
                        del pool_new[1]
                    fork(pool_new, state_new, group_new)
        fork(pool, state, '')
        return answer

if __name__ == '__main__':
    so = Solution()
    for ans in so.generateParenthesis(3):
        print(ans)
    print(so.generateParenthesis(1))
